package offer.zixing.chapter15;

import java.util.*;

public class Test109 {
    public static void main(String[] args) {
        String[] deadends = {"0201", "0101", "0102", "1212", "2002"};
        String target = "0202";
        System.out.println(openLock2(deadends, target));
    }

    public static int openLock(String[] deadends, String target) {
        Set<String> dead = new HashSet<>(Arrays.asList(deadends));
        String init = "0000";
        // 自锁
        if (dead.contains(init) || dead.contains(target)) {
            return -1;
        }
        // 记录已经拨过的组合
        Set<String> visited = new HashSet<>();
        visited.add(init);
        Queue<String> queue1 = new LinkedList<>();
        queue1.add(init);
        Queue<String> queue2 = new LinkedList<>();
        int steps = 0;
        while (!queue1.isEmpty()) {
            String cur = queue1.poll();
            if (cur.equals(target)) {
                return steps;
            }
            // 获取相邻节点
            List<String> neighbors = getNeighbors(cur);
            for (String neighbor : neighbors) {
                // 不会死锁 且 没有拨过才执行
                if (!dead.contains(neighbor) && !visited.contains(neighbor)) {
                    queue2.add(neighbor);
                    visited.add(neighbor);
                }
            }
            if (queue1.isEmpty()) {
                steps++;
                queue1 = queue2;
                queue2 = new LinkedList<>();
            }
        }
        return -1;
    }

    private static List<String> getNeighbors(String cur) {
        List<String> list = new LinkedList<>();
        // 每一个轮子会曾1或者减1,4个轮子下一次会出现 8 个相邻节点
        for (int i = 0; i < cur.length(); i++) {
            char ch = cur.charAt(i);
            StringBuilder sb = new StringBuilder(cur);
            // 减值转动
            char newCh = ch == '0' ? '9' : (char) (ch - 1);
            sb.setCharAt(i, newCh);
            list.add(sb.toString());
            // 增值转动
            newCh = ch == '9' ? '0' : (char) (ch + 1);
            sb.setCharAt(i, newCh);
            list.add(sb.toString());
        }
        return list;
    }

    public static int openLock2(String[] deadends, String target) {
        String init = "0000";
        Set<String> dead = new HashSet<>(Arrays.asList(deadends));
        // 自锁
        if (dead.contains(init) || dead.contains(target)) {
            return -1;
        }
        if (target.equals(init)) {
            return 0;
        }
        // 记录已经拨过的组合
        Set<String> visited = new HashSet<>();
        visited.add(init);
        Set<String> set1 = new HashSet<>();
        set1.add(init);
        Set<String> set2 = new HashSet<>();
        set2.add(target);
        // 双向计算时，至少需要走一次，特殊情况是 target.equals(init)
        int steps = 1;
        while (!set1.isEmpty() && !set2.isEmpty()) {
            // 优化取值
            if (set2.size() < set1.size()) {
                Set<String> temp = set1;
                set1 = set2;
                set2 = temp;
            }
            Set<String> set3 = new HashSet<>();
            for (String cur : set1) {
                List<String> neighbors = getNeighbors(cur);
                for (String neighbor : neighbors) {
                    if (set2.contains(neighbor)) {
                        return steps;
                    }
                    if (!dead.contains(neighbor) && !visited.contains(neighbor)) {
                        set3.add(neighbor);
                        visited.add(neighbor);
                    }
                }
            }
            steps++;
            set1 = set3;
        }
        return -1;
    }
}
